Non-increasing sequences of values may be encountered in many areas of computer science. In particular, non-increasing sequences of values may be generated by a variety of compression techniques to represent different facets of the compression technique. For example, traditional entropy encoding compression algorithms may generate non-increasing sequences of values to model escape code counts, as described below. A mechanism to efficiently code these non-increasing sequences of values would be beneficial.
Traditional entropy encoding compression algorithms (such as Huffman coding, adaptive Huffman coding or arithmetic coding) depend on having a statistical model of the input stream they are compressing. The more accurately the model represents the actual statistical properties of symbols in the input stream, the better the algorithm is able to compress the stream. Loosely speaking, the model is used to make a prediction about what input symbol will come next in the input stream.
The probability model can be static (i.e., unchanging for the duration of a compression process) or adaptive (i.e., evolving as the compressor processes the input data stream). An adaptive model typically works by matching the current input symbol against its prediction context, and if it finds the current input symbol in its context, generating a code representing the particular probability range that the input symbol represents. For example, if the current input symbol is ‘e’ and the model predicts that the probability of ‘e’ is in the range 0.13 to 0.47, then the compressor would generate an output code representing that probability range. This “code and update” cycle is repeated until there are no more input symbols to compress.
When the compressor encounters a new symbol for which its model has no prediction, it must do something else. Consequently, a solution to address new symbols by the model includes encoding a special “escape” symbol to signal to the decompressor that the next symbol is a literal value. The escapes are used because the other option of including every possible symbol in every context leads to a poor performance (including possible data expansion).
Techniques have been discovered to determine optimal sequences of escape counts to assign to compression algorithm models to minimize the total number of bits generated for the coding stream. However, this optimal sequence of escape counts needs to be communicated between the various components of the compression algorithm model, and can lead to inefficiencies that nullify any gains obtained by determining the optimal sequence of escape counts. Many times, this sequence of escape counts is a non-increasing sequence of values. A mechanism to code a non-increasing sequence of values in an efficient manner for communication would be beneficial.